package java学习.leetcode.editor.cn;

import java.util.Arrays;

/**
 * @author 刘世锦
 * 2022-09-23 14:03:28	 当前时间
 */
//给你一个整数数组 nums 和一个整数 target 。 
//
// 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ： 
//
// 
// 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 
// 
//
// 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,1,1,1], target = 3
//输出：5
//解释：一共有 5 种方法让最终目标和为 3 。
//   -1 + 1 + 1 + 1 + 1 = 3
//   +1 - 1 + 1 + 1 + 1 = 3
//   +1 + 1 - 1 + 1 + 1 = 3
//   +1 + 1 + 1 - 1 + 1 = 3
//   +1 + 1 + 1 + 1 - 1 = 3
// 
//
// 示例 2： 
//
// 
//输入：nums = [1], target = 1
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 20 
// 0 <= nums[i] <= 1000 
// 0 <= sum(nums[i]) <= 1000 
// -1000 <= target <= 1000 
// 
// Related Topics 数组 动态规划 回溯 
// 👍 1381 👎 0

public class 目标和{
	public static void main(String[] args) {
		Solution solution = new 目标和().new Solution();
		int[] nums = {1,1,1,1,1};
		int target = 3;
		System.out.println(solution.findTargetSumWays(nums, target));
		System.out.println(solution.findTargetSumWaysP(nums, target));
	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
		/**
		 * 一共有5种方法让最终目标和为3。
		 *  正-负=sum
		 *  正+负=S
		 *  2 正 = sum+S
		 * 即：要最终结果为S，就是求放入正数符号的最大个数.
		 *  在背包为plus中，装满的方法数. w[] = v[] = nums[]
		 *
		 */
		int sum = 0;
		for (int num : nums) {
			sum+=num;
		}
		int plus = (sum+target);
		if (plus%2!=0||plus<0){
			return 0;
		}
		int bagsize = plus >>1;
		int[] dp = new int[bagsize+1];
		dp[0] = 1;
//		先遍历物品再遍历背包，  todo 01背包  是背包容量倒序
		for (int i = 0; i <nums.length ; i++) {
			for (int j = bagsize; j >=nums[i] ; j--) {
				dp[j] += dp[j-nums[i]];
			}
		}

//		System.out.println(Arrays.toString(dp));
		return dp[bagsize];
	}
	public  int findTargetSumWaysP(int[] nums, int target) {
		int n = nums.length;
		int sum = 0;
		for (int num : nums) {
			sum+=num;
		}
		int plus = target+sum;

		// 因为要是 正整数
		if ((plus)%2!=0 || plus <0){
			return  0;
		}
		int bagsize = (plus)/2;

		int[] dp = new int[bagsize+1];
		dp[0] = 1;

		for (int i = 0; i < n; i++) {
//            i 依旧从0开始0 ： 因为 dp[j] 需要dp【0】
			for (int j = bagsize; j >=nums[i] ; j--) {
				dp[j] += dp[j-nums[i]];

			}
		}
		System.out.println(Arrays.toString(dp));
		return dp[bagsize];
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
